package com.learngit;

import java.util.ArrayList;
import java.util.List;

public class Experiment_8 {
    /*
    找出一个整数数组中子数组之和的最大值，例如：数组[1, -2, 3, 5, -1]，返回8（因为符合要求的子数组是 [3, 5]）；
    数组[1, -2, 3, -8, 5, 1]，返回6（因为符合要求的子数组是 [5, 1]）;
    数组[1, -2, 3,-2, 5, 1]，返回7（因为符合要求的子数组是 [3, -2, 5, 1]）。
    * */
    public static void main(String[] args) {
        //一、	1->2->8
        //输入空数组:[]，预期输出0
        int[] testList_1 = new int[]{};
        System.out.println("预计输出："+0+",实际输出"+MaxSubSumOfSequence(testList_1));
        //二、	1->2->3->4->5->6->7->2->8
        //输入数组：[1,2]，预计输出3
        int[] testList_2 = new int[]{1,2};
        System.out.println("预计输出："+3+",实际输出"+MaxSubSumOfSequence(testList_2));
        //三、	1->2->3->4->6->7->2->8
        //输入数组：[1,-2,1]，预计输出1
        int[] testList_3 = new int[]{1,-2,1};
        System.out.println("预计输出："+1+",实际输出"+MaxSubSumOfSequence(testList_3));
        //四、	1->2->3->4->6->2->8
        //输入数组:[3,-1]，预计输出3
        int[] testList_4 = new int[]{3,-1};
        System.out.println("预计输出："+3+",实际输出"+MaxSubSumOfSequence(testList_4));
    }

    /**
     *  在线处理算法计算最大子序列
     * @param list
     * @return
     */
    public static int MaxSubSumOfSequence(int[] list){
        int thisSum = 0,maxSum = 0;
        for(int i=0;i<list.length;i++){
            thisSum += list[i];
            if(thisSum > maxSum){
                maxSum = thisSum;
            }
            if(thisSum < 0){
                thisSum = 0;
            }
        }
        return maxSum;
    }
}


